package com.lee.algorithm.sort.quick;

import static com.lee.algorithm.sort.SortUtil.print;
import static com.lee.algorithm.sort.SortUtil.swap;

/***
 * @description 两区域划分
 * @author 青石路
 * @date 2022/3/13 16:53
 */
public class TwoRange {

    public static void main(String[] args) {
        int[] arr = new int[]{9,8,3,2,6,4,5,0,1,1,1};
        // int[] newArr = split(arr, 7);
        print(arr);
        splitPlus(arr, 7);
        print(arr);
    }

    /**
     * 两区域划分
     *      小于等于放左边，大于放右边
     * @param arr
     * @param target
     * @author 博客园 @ 青石路
     */
    public static int[] split(int[] arr, int target) {
        if (arr == null || arr.length == 0) {
            return arr;
        }
        int[] newArr = new int[arr.length];
        // lte：小于等于区域索引下标，gt：大于区域索引下标
        int lte = 0, gt = arr.length - 1;

        for(int i=0; i<arr.length; i++) {
            if (arr[i] <= target) {
                newArr[lte++] = arr[i];
            } else {
                newArr[gt--] = arr[i];
            }
        }
        return newArr;
    }

    /**
     * 两区域划分
     *      小于等于放左边，大于放右边
     * @param arr
     * @param target
     * @author 博客园 @ 青石路
     */
    public static void splitPlus(int[] arr, int target) {

        if (arr == null || arr.length == 0) {
            return;
        }

        int lte = -1;

        /**
         * 1.1 arr[i] <= target，则 arr[i] 与左边界的下一个元素进行交换，边界右移，i++
         * 1.2 arr[i] > target，边界不动，i++
         *
         * 两种情况都有 i++，可以作为 for 循环的第三个表达式
         */
        for(int i=0; i<arr.length; i++) {
            if (arr[i] <= target) {
                // ++lte，既用于取左边界的下一个元素，也实现了右移
                swap(arr, ++lte, i);
            }
        }
    }
}
